package com.ttx.algorithm.leetcode.dp;

import java.util.ArrayList;
import java.util.List;

/**
 * 5. 最长回文子串
 *
 *  给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 *
 *  示例 1：
 *
 *  输入: "babad"
 *  输出: "bab"
 *  注意: "aba" 也是一个有效答案。
 *
 *  示例 2：
 *
 *  输入: "cbbd"
 *  输出: "bb"
 *
 * @author TimFruit
 * @date 19-10-13 上午8:05
 */
public class P005LongestPalindrome {

    public String longestPalindrome(String s) {
        if(s==null || s.length()==0){
            return "";
        }
        // 循环找到1个回文, (单个或双个), 最后拓展
        char[] chars=s.toCharArray();
        List<Integer> start=new ArrayList<Integer>(); //回文起始下标
        List<Integer> len=new ArrayList<Integer>();  //对应长度

        int l, r; //回文的最左下标, 和 最右下标
        for(int i=0,size=chars.length; i<size ;i++){

            //起始回文 "aa" 形式
            l=i;
            r=i+1;

            while(l>=0 && r<size && chars[l]==chars[r]){
                start.add(l);
                len.add(r-l+1);
                l--;
                r++;
            }

            //起始回文 "b" 形式
            l=i;
            r=i;
            while(l>=0 && r<size && chars[l]==chars[r]){
                start.add(l);
                len.add(r-l+1);
                l--;
                r++;
            }

        }


        // 寻找最大的回文
        int maxLen=0;
        int maxStartIndex=0;

        for(int i=0; i<len.size(); i++){
            if(len.get(i)>maxLen){
                maxLen=len.get(i);
                maxStartIndex=start.get(i);
            }
        }


        return s.substring(maxStartIndex, maxStartIndex+maxLen);


    }



}
